<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
<html xmlns="http://www.w3.org/1999/xhtml">
<head>
  <meta http-equiv="Content-Type" content="text/html; charset=utf-8" />
  <meta http-equiv="Content-Style-Type" content="text/css" />
  <meta name="generator" content="pandoc" />
  <title>力扣算法题解笔记</title>
  <style type="text/css">code{white-space: pre;}</style>
  <style type="text/css">
div.sourceCode { overflow-x: auto; }
table.sourceCode, tr.sourceCode, td.lineNumbers, td.sourceCode {
  margin: 0; padding: 0; vertical-align: baseline; border: none; }
table.sourceCode { width: 100%; line-height: 100%; }
td.lineNumbers { text-align: right; padding-right: 4px; padding-left: 4px; color: #aaaaaa; border-right: 1px solid #aaaaaa; }
td.sourceCode { padding-left: 5px; }
code > span.kw { color: #007020; font-weight: bold; } /* Keyword */
code > span.dt { color: #902000; } /* DataType */
code > span.dv { color: #40a070; } /* DecVal */
code > span.bn { color: #40a070; } /* BaseN */
code > span.fl { color: #40a070; } /* Float */
code > span.ch { color: #4070a0; } /* Char */
code > span.st { color: #4070a0; } /* String */
code > span.co { color: #60a0b0; font-style: italic; } /* Comment */
code > span.ot { color: #007020; } /* Other */
code > span.al { color: #ff0000; font-weight: bold; } /* Alert */
code > span.fu { color: #06287e; } /* Function */
code > span.er { color: #ff0000; font-weight: bold; } /* Error */
code > span.wa { color: #60a0b0; font-weight: bold; font-style: italic; } /* Warning */
code > span.cn { color: #880000; } /* Constant */
code > span.sc { color: #4070a0; } /* SpecialChar */
code > span.vs { color: #4070a0; } /* VerbatimString */
code > span.ss { color: #bb6688; } /* SpecialString */
code > span.im { } /* Import */
code > span.va { color: #19177c; } /* Variable */
code > span.cf { color: #007020; font-weight: bold; } /* ControlFlow */
code > span.op { color: #666666; } /* Operator */
code > span.bu { } /* BuiltIn */
code > span.ex { } /* Extension */
code > span.pp { color: #bc7a00; } /* Preprocessor */
code > span.at { color: #7d9029; } /* Attribute */
code > span.do { color: #ba2121; font-style: italic; } /* Documentation */
code > span.an { color: #60a0b0; font-weight: bold; font-style: italic; } /* Annotation */
code > span.cv { color: #60a0b0; font-weight: bold; font-style: italic; } /* CommentVar */
code > span.in { color: #60a0b0; font-weight: bold; font-style: italic; } /* Information */
  </style>
  <link rel="stylesheet" href="doc/linux-style.css" type="text/css" />
</head>
<body>
<div id="header">
<h1 class="title">力扣算法题解笔记</h1>
</div>
<div id="TOC">
<ul>
<li><a href="#力扣算法题解笔记">力扣算法题解笔记</a><ul>
<li><a href="#三数之和">15. 三数之和</a></li>
<li><a href="#接雨水">42. 接雨水</a></li>
<li><a href="#无重复字符的最长子串">3. 无重复字符的最长子串</a></li>
<li><a href="#滑动窗口最大值">239. 滑动窗口最大值</a></li>
<li><a href="#最小覆盖子串">76. 最小覆盖子串</a></li>
<li><a href="#缺失的第一个正数">41. 缺失的第一个正数</a></li>
<li><a href="#旋转图像">48. 旋转图像</a></li>
<li><a href="#电话号码的字母组合">17. 电话号码的字母组合</a></li>
<li><a href="#组合总和">39. 组合总和</a></li>
<li><a href="#单词搜索">79. 单词搜索</a></li>
<li><a href="#搜索二维矩阵">74. 搜索二维矩阵</a></li>
<li><a href="#有效的括号">20. 有效的括号</a></li>
<li><a href="#字符串解码">394. 字符串解码</a></li>
<li><a href="#每日温度">739. 每日温度</a></li>
<li><a href="#前k个高频元素">347. 前K个高频元素</a></li>
<li><a href="#lru缓存">146 LRU缓存</a></li>
<li><a href="#最长回子串">5 最长回子串</a></li>
<li><a href="#寻找两个有序数组的中位数">4 寻找两个有序数组的中位数</a></li>
<li><a href="#两数相加">2 两数相加</a></li>
<li><a href="#快速排序">快速排序</a></li>
<li><a href="#归并排序">归并排序</a></li>
<li><a href="#堆排序">堆排序</a></li>
</ul></li>
</ul>
</div>
<h1 id="力扣算法题解笔记">力扣算法题解笔记</h1>
<h2 id="三数之和">15. 三数之和</h2>
<ul>
<li><strong>方法</strong>：双指针法</li>
<li><strong>关键点</strong>：</li>
<li><code>i</code> 去重：检查 <code>nums[i]</code> 是否与前一个元素相同，避免重复。</li>
<li>双指针循环：使用 <code>while (j &lt; k)</code> 遍历。</li>
<li><code>j</code> 和 <code>k</code> 去重：在找到有效三元组后，跳过重复的 <code>j</code> 和 <code>k</code>。</li>
<li><p><strong>代码逻辑</strong>：</p>
<div class="sourceCode"><pre class="sourceCode c"><code class="sourceCode c"><span class="cf">while</span> j &lt; k:
<span class="cf">if</span> sum == <span class="dv">0</span>:
<span class="co">//处理结果并移动j和k</span>
<span class="cf">while</span> j &lt; k and nums[j] == nums[j+<span class="dv">1</span>]: j +=<span class="dv">1</span>
<span class="cf">while</span> j &lt; k and nums[k] == nums[k<span class="dv">-1</span>]: k -=<span class="dv">1</span>
j +=<span class="dv">1</span>; k -=<span class="dv">1</span></code></pre></div></li>
</ul>
<h2 id="接雨水">42. 接雨水</h2>
<h3 id="方法1动态规划">方法1：动态规划</h3>
<ul>
<li><strong>步骤</strong>：</li>
</ul>
<ol style="list-style-type: decimal">
<li>预计算左侧最大值数组 <code>ldp</code> 和右侧最大值数组 <code>rdp</code>。</li>
<li>对每个位置取 <code>min(ldp[i], rdp[i]) - height[i]</code> 累加。</li>
</ol>
<h3 id="方法2双指针优化">方法2：双指针优化</h3>
<ul>
<li><strong>关键点</strong>：</li>
<li>维护 <code>lmax</code> 和 <code>rmax</code> 分别表示左右遍历时的最大值。</li>
<li>当 <code>height[left] &lt;= height[right]</code> 时处理左指针，反之处理右指针。</li>
<li><strong>公式</strong>：<code>ans += (lmax - height[left])</code> 或 <code>ans += (rmax - height[right])</code>。</li>
</ul>
<h2 id="无重复字符的最长子串">3. 无重复字符的最长子串</h2>
<ul>
<li><strong>方法</strong>：滑动窗口（Set实现）</li>
<li><strong>关键点</strong>：</li>
<li>使用 <code>set</code> 记录当前窗口字符。</li>
<li>当遇到重复字符时，移动左指针并删除对应字符，直到无重复。</li>
<li><strong>注意</strong>：用 <code>while</code> 循环处理重复字符的移除。</li>
</ul>
<div class="sourceCode"><pre class="sourceCode cpp"><code class="sourceCode cpp"><span class="kw">class</span> Solution {
<span class="kw">public</span>:
    <span class="dt">int</span> lengthOfLongestSubstring(string s) {
        <span class="dt">int</span> j=<span class="dv">0</span>;
        <span class="dt">int</span> maxLength =<span class="dv">0</span>;
        unordered_set&lt;<span class="dt">char</span>&gt; charIndexSet;
        <span class="cf">for</span>(<span class="dt">int</span> i=<span class="dv">0</span>; i&lt;s.size();i++){
            <span class="cf">while</span>(charIndexSet.find(s[i]) != charIndexSet.end()){
                charIndexSet.erase(s[j]);
                j++;
            }
            charIndexSet.insert(s[i]);
            maxLength =max(maxLength,i-j<span class="dv">+1</span>);
        }
        <span class="cf">return</span> maxLength;
    }
};</code></pre></div>
<h2 id="滑动窗口最大值">239. 滑动窗口最大值</h2>
<ul>
<li><strong>方法</strong>：单调递减双端队列</li>
<li><strong>步骤</strong>：</li>
</ul>
<ol style="list-style-type: decimal">
<li>队列保存索引，且队列对应值单调递减。</li>
<li>窗口滑动时，移除超出窗口范围的队首元素。</li>
<li>新元素入队前，移除队尾小于它的元素。</li>
<li>当窗口形成后（<code>i &gt;= k-1</code>），队首即为最大值。</li>
</ol>
<h2 id="最小覆盖子串">76. 最小覆盖子串</h2>
<ul>
<li><strong>方法</strong>：滑动窗口 + 哈希表</li>
<li><strong>关键点</strong>：</li>
<li>用数组统计 <code>t</code> 中字符出现次数，维护窗口内字符覆盖状态。</li>
<li>扩展右指针直到覆盖 <code>t</code>，然后收缩左指针找最小窗口。</li>
<li><strong>优化</strong>：用 <code>count</code> 变量记录匹配字符数，避免每次检查全表。</li>
</ul>
<h2 id="缺失的第一个正数">41. 缺失的第一个正数</h2>
<ul>
<li><strong>方法</strong>：原地哈希</li>
<li><strong>步骤</strong>：</li>
</ul>
<ol style="list-style-type: decimal">
<li>遍历数组，将正整数 <code>nums[i]</code> 交换到索引 <code>nums[i]-1</code> 的位置。</li>
<li>再次遍历，找到第一个不满足 <code>nums[i] == i+1</code> 的位置。</li>
<li><strong>边界</strong>：若全匹配，返回 <code>n+1</code>。</li>
</ol>
<h2 id="旋转图像">48. 旋转图像</h2>
<ul>
<li><strong>方法</strong>：数学变换</li>
<li><strong>步骤</strong>：</li>
</ul>
<ol style="list-style-type: decimal">
<li><strong>转置矩阵</strong>：交换 <code>matrix[i][j]</code> 与 <code>matrix[j][i]</code>。</li>
<li><strong>水平翻转每行</strong>：交换 <code>matrix[i][j]</code> 与 <code>matrix[i][n-j-1]</code>。</li>
</ol>
<h2 id="电话号码的字母组合">17. 电话号码的字母组合</h2>
<ul>
<li><strong>方法</strong>：回溯算法</li>
<li><strong>关键点</strong>：</li>
<li>递归终止条件：路径长度等于数字串长度。</li>
<li>遍历当前数字对应的所有字母，回溯选择与撤销。</li>
<li><strong>参数</strong>：<code>index</code> 表示当前处理的数字位置。</li>
</ul>
<h2 id="组合总和">39. 组合总和</h2>
<ul>
<li><strong>方法</strong>：回溯 + 剪枝</li>
<li><strong>关键点</strong>：</li>
<li>允许重复选择元素，递归时 <code>start</code> 参数不变。</li>
<li>排序后剪枝：若当前候选数大于剩余和，提前终止。</li>
</ul>
<h2 id="单词搜索">79. 单词搜索</h2>
<ul>
<li><strong>方法</strong>：DFS + 回溯</li>
<li><strong>关键点</strong>：</li>
<li>终止条件：索引达到单词长度或字符不匹配。</li>
<li>标记已访问位置，递归后恢复状态。</li>
<li><strong>注意</strong>：四个方向的DFS需处理越界问题。</li>
</ul>
<h2 id="搜索二维矩阵">74. 搜索二维矩阵</h2>
<ul>
<li><strong>方法</strong>：二分查找</li>
<li><strong>关键点</strong>：</li>
<li>将二维矩阵视为一维数组，计算中间元素的坐标：<code>mid_val = matrix[mid//n][mid%n]</code>。</li>
<li>根据 <code>mid_val</code> 与 <code>target</code> 的关系调整搜索范围。</li>
</ul>
<h2 id="有效的括号">20. 有效的括号</h2>
<ul>
<li><strong>方法</strong>：栈</li>
<li><strong>关键点</strong>：</li>
<li>遇到左括号入栈，右括号时检查栈顶是否匹配。</li>
<li><strong>边界处理</strong>：栈为空时遇到右括号直接返回False。</li>
</ul>
<h2 id="字符串解码">394. 字符串解码</h2>
<ul>
<li><strong>方法</strong>：双栈（数字栈 + 字符串栈）</li>
<li><strong>步骤</strong>：</li>
</ul>
<ol style="list-style-type: decimal">
<li>遇到数字时解析完整数值入数字栈。</li>
<li>遇到 <code>[</code> 时，当前字符串入栈并重置。</li>
<li>遇到 <code>]</code> 时，弹出数字和字符串，拼接后更新结果。</li>
</ol>
<h2 id="每日温度">739. 每日温度</h2>
<ul>
<li><strong>方法</strong>：单调栈</li>
<li><strong>关键点</strong>：</li>
<li>栈保存温度递减的日期索引。</li>
<li>遍历时若当前温度大于栈顶温度，弹出并计算天数差。</li>
<li><strong>结果数组</strong>：<code>ans[stack.pop()] = i - idx</code></li>
</ul>
<h2 id="前k个高频元素">347. 前K个高频元素</h2>
<ul>
<li><strong>方法</strong>：最小堆（优先队列）</li>
<li><strong>步骤</strong>：</li>
</ul>
<ol style="list-style-type: decimal">
<li>统计频率存入哈希表。</li>
<li>维护大小为 <code>k</code> 的最小堆，按频率排序。</li>
<li>遍历哈希表，堆满后弹出较小频率元素。</li>
</ol>
<div class="sourceCode"><pre class="sourceCode c"><code class="sourceCode c">class Solution {

    <span class="kw">struct</span> myComparison{
        bool operator()(pair&lt;<span class="dt">int</span>,<span class="dt">int</span>&gt;&amp;p1,pair&lt;<span class="dt">int</span>,<span class="dt">int</span>&gt;&amp;p2){
            <span class="cf">return</span> p1.second&gt;p2.second;<span class="co">//小顶堆是大于号</span>
        }
    };

public:
    vector&lt;<span class="dt">int</span>&gt; topKFrequent(vector&lt;<span class="dt">int</span>&gt;&amp; nums, <span class="dt">int</span> k) {
        unordered_map&lt;<span class="dt">int</span>, <span class="dt">int</span>&gt; map;
        <span class="cf">for</span>(<span class="dt">int</span> i=<span class="dv">0</span>; i&lt;nums.size(); i++){
            map[nums[i]]++;  
        }

        priority_queue&lt;pair&lt;<span class="dt">int</span>, <span class="dt">int</span>&gt;, vector&lt;pair&lt;<span class="dt">int</span>, <span class="dt">int</span>&gt;&gt;,myComparison&gt; pri_que;
        <span class="cf">for</span>(<span class="dt">auto</span>&amp; it: map){
            pri_que.push(it);
            <span class="cf">if</span>(pri_que.size() &gt;k){
                pri_que.pop();
            }
        }

        vector&lt;<span class="dt">int</span>&gt; res;
        <span class="cf">while</span>(!pri_que.empty()){
            res.emplace_back(pri_que.top().first);
            pri_que.pop();
        }
        <span class="cf">return</span> res;
    }
};</code></pre></div>
<h2 id="lru缓存">146 LRU缓存</h2>
<ul>
<li><strong>方法</strong>：双向链表、哈希表</li>
<li><strong>步骤</strong>:</li>
</ul>
<ol style="list-style-type: decimal">
<li>设计一个双向链表，实现push_fornt函数、remove_node函数、get_node函数</li>
<li>push_fornt函数是在链表头部添加一个结点,实现操作如下所示： <code>x-&gt;pre =dummy; x-&gt;next=dummy-&gt;next;x-&gt;pre-&gt;next =x;x-&gt;next-&gt;pre =x;</code></li>
<li>remove_node函数是删除一个结点，实现如下： <code>x-&gt;pre-&gt;next = x-&gt;next;x-&gt;next-&gt;pre = x-&gt;pre;</code></li>
<li>get_node函数是获取key对应的节点，同时把该节点移动到链表头部，操作如下所示： <code>用hashmap通过key找到node，先remove结点node，然后再push_front结点</code><br />
</li>
<li>LRU的每次Put操作，需要先判断结点是否存在该hashmap中，存在则直接替换key对应的值，不存在则放到链表头部，如果hashmap的大小大于了LRU缓存大小，那么则删除hashmap中对应的key，删除链表中最后一个结点。注<code>用DLinkedNode* back_node = dummy-&gt;pre;</code>获取最后一个结点</li>
</ol>
<div class="sourceCode"><pre class="sourceCode c"><code class="sourceCode c"><span class="kw">struct</span> Dlinked {
    <span class="dt">int</span> key, value;
    Dlinked *next, *pre;
    Dlinked(<span class="dt">int</span> _key, <span class="dt">int</span> _value) : key(_key), value(_value), next(nullptr), pre(nullptr) {}
};

class LRUCache {
private:
    <span class="dt">int</span> capacity;
    Dlinked* dummy;
    unordered_map&lt;<span class="dt">int</span>, Dlinked*&gt; key_to_node;

    <span class="dt">void</span> remove_node(Dlinked* x) {
        x-&gt;pre-&gt;next = x-&gt;next;
        x-&gt;next-&gt;pre = x-&gt;pre;
    }

    <span class="dt">void</span> push_front(Dlinked* x) {
        x-&gt;next = dummy-&gt;next;
        x-&gt;pre = dummy;
        x-&gt;pre-&gt;next = x;
        x-&gt;next-&gt;pre = x;
    }

    Dlinked* get_node(<span class="dt">int</span> key) {
        <span class="dt">auto</span> it = key_to_node.find(key);
        <span class="cf">if</span> (it == key_to_node.end()) <span class="cf">return</span> nullptr;
        Dlinked* node = it-&gt;second;
        remove_node(node);
        push_front(node);
        <span class="cf">return</span> node;
    }

public:
    LRUCache(<span class="dt">int</span> capacity) {
        this-&gt;capacity = capacity;
        dummy = new Dlinked(<span class="dv">0</span>, <span class="dv">0</span>);
        dummy-&gt;pre = dummy;
        dummy-&gt;next = dummy;
    }

    <span class="dt">int</span> get(<span class="dt">int</span> key) {
        Dlinked* node = get_node(key);
        <span class="cf">return</span> node ? node-&gt;value : <span class="dv">-1</span>;
    }

    <span class="dt">void</span> put(<span class="dt">int</span> key, <span class="dt">int</span> value) {
        Dlinked* node = get_node(key);
        <span class="cf">if</span> (node) {
            node-&gt;value = value;
            <span class="cf">return</span>;
        }
        node = new Dlinked(key, value);
        key_to_node[key] = node;
        push_front(node);
        <span class="cf">if</span> (key_to_node.size() &gt; capacity) {
            Dlinked* back_node = dummy-&gt;pre;
            remove_node(back_node);
            key_to_node.erase(back_node-&gt;key);
            delete back_node;
        }
    }
};</code></pre></div>
<h2 id="最长回子串">5 最长回子串</h2>
<ul>
<li><strong>方法一</strong>：中心拓展法(偶数拓展，奇数拓展)</li>
<li><strong>步骤</strong>:
<ol style="list-style-type: decimal">
<li>编写一个从中心拓展的回文字符串判断。</li>
<li>从头遍历，i作为中心点往外拓展，可以以奇数个拓展，也可以以偶数个拓展。</li>
<li>存储并且比较每次中心的的偶数、奇数拓展长度，返回最长回文子串</li>
</ol></li>
</ul>
<div class="sourceCode"><pre class="sourceCode c"><code class="sourceCode c">    pair&lt;<span class="dt">int</span>,<span class="dt">int</span>&gt; expandFormCenter(string s,<span class="dt">int</span> left, <span class="dt">int</span> right){
        <span class="cf">while</span>(left &gt;=<span class="dv">0</span> &amp;&amp; right &lt; s.size()&amp;&amp; s[left] == s[right]){
            left --;
            right ++;
        }
        <span class="cf">return</span> {left+<span class="dv">1</span>, right<span class="dv">-1</span>};
    } 

    string longestPalindrome(string s) {
        
        <span class="dt">int</span> start = <span class="dv">0</span>,end = <span class="dv">0</span>;
        <span class="cf">for</span> (<span class="dt">int</span> i = <span class="dv">0</span>; i &lt; s.size(); i++) {
            <span class="dt">auto</span> [left1, right1] = expandFormCenter(s, i, i);
            <span class="dt">auto</span> [left2, right2] = expandFormCenter(s, i, i + <span class="dv">1</span>);
            
            <span class="dt">int</span> len1 = right1 - left1 + <span class="dv">1</span>;
            <span class="dt">int</span> len2 = right2 - left2 + <span class="dv">1</span>;
            <span class="dt">int</span> curr_len = end - start + <span class="dv">1</span>; 
    
            <span class="cf">if</span> (left1 &lt;= right1 &amp;&amp; len1 &gt; curr_len) {
                start = left1;
                end = right1;
            }
            <span class="cf">if</span> (left2 &lt;= right2 &amp;&amp; len2 &gt; curr_len) {
                start = left2;
                end = right2;
            }
        }
        <span class="cf">return</span> s.substr(start,end-start + <span class="dv">1</span>);
    }</code></pre></div>
<ul>
<li><strong>方法二</strong>：动态规划</li>
</ul>
<h2 id="寻找两个有序数组的中位数">4 寻找两个有序数组的中位数</h2>
<ul>
<li><strong>方法</strong>：二分法</li>
<li><strong>步骤</strong>:
<ol style="list-style-type: decimal">
<li>就是要转换成从两个有序数组中找出第k个大的元素。</li>
<li>需要每次判断A[K/2-1]与B[K/2-1]的值，判断完后就可以舍弃k/2个值，更新k的值。然后再将舍弃后的值进行判断。</li>
<li>最后如果一个数组为空，说明该数组中的所有元素都被排除，我们可以直接返回另一个数组中第 k 小的元素。如果 k=1，我们只要返回两个数组首元素的最小值即可。</li>
</ol></li>
</ul>
<div class="sourceCode"><pre class="sourceCode c"><code class="sourceCode c">class Solution {
    public:
        <span class="dt">int</span> getKthElement(<span class="dt">const</span> vector&lt;<span class="dt">int</span>&gt;&amp; nums1, <span class="dt">const</span> vector&lt;<span class="dt">int</span>&gt;&amp; nums2, <span class="dt">int</span> k) {
            <span class="co">/* 主要思路：要找到第 k (k&gt;1) 小的元素，那么就取 pivot1 = nums1[k/2-1] 和 pivot2 = nums2[k/2-1] 进行比较</span>
<span class="co">             * 这里的 &quot;/&quot; 表示整除</span>
<span class="co">             * nums1 中小于等于 pivot1 的元素有 nums1[0 .. k/2-2] 共计 k/2-1 个</span>
<span class="co">             * nums2 中小于等于 pivot2 的元素有 nums2[0 .. k/2-2] 共计 k/2-1 个</span>
<span class="co">             * 取 pivot = min(pivot1, pivot2)，两个数组中小于等于 pivot 的元素共计不会超过 (k/2-1) + (k/2-1) &lt;= k-2 个</span>
<span class="co">             * 这样 pivot 本身最大也只能是第 k-1 小的元素</span>
<span class="co">             * 如果 pivot = pivot1，那么 nums1[0 .. k/2-1] 都不可能是第 k 小的元素。把这些元素全部 &quot;删除&quot;，剩下的作为新的 nums1 数组</span>
<span class="co">             * 如果 pivot = pivot2，那么 nums2[0 .. k/2-1] 都不可能是第 k 小的元素。把这些元素全部 &quot;删除&quot;，剩下的作为新的 nums2 数组</span>
<span class="co">             * 由于我们 &quot;删除&quot; 了一些元素（这些元素都比第 k 小的元素要小），因此需要修改 k 的值，减去删除的数的个数</span>
<span class="co">             */</span>
    
            <span class="dt">int</span> m = nums1.size();
            <span class="dt">int</span> n = nums2.size();
            <span class="dt">int</span> index1 = <span class="dv">0</span>, index2 = <span class="dv">0</span>;
    
            <span class="cf">while</span> (true) {
                <span class="co">// 边界情况</span>
                <span class="cf">if</span> (index1 == m) {
                    <span class="cf">return</span> nums2[index2 + k - <span class="dv">1</span>];
                }
                <span class="cf">if</span> (index2 == n) {
                    <span class="cf">return</span> nums1[index1 + k - <span class="dv">1</span>];
                }
                <span class="cf">if</span> (k == <span class="dv">1</span>) {
                    <span class="cf">return</span> min(nums1[index1], nums2[index2]);
                }
    
                <span class="co">// 正常情况</span>
                <span class="dt">int</span> newIndex1 = min(index1 + k / <span class="dv">2</span> - <span class="dv">1</span>, m - <span class="dv">1</span>);
                <span class="dt">int</span> newIndex2 = min(index2 + k / <span class="dv">2</span> - <span class="dv">1</span>, n - <span class="dv">1</span>);
                <span class="dt">int</span> pivot1 = nums1[newIndex1];
                <span class="dt">int</span> pivot2 = nums2[newIndex2];
                <span class="cf">if</span> (pivot1 &lt;= pivot2) {
                    k -= newIndex1 - index1 + <span class="dv">1</span>;
                    index1 = newIndex1 + <span class="dv">1</span>;
                }
                <span class="cf">else</span> {
                    k -= newIndex2 - index2 + <span class="dv">1</span>;
                    index2 = newIndex2 + <span class="dv">1</span>;
                }
            }
        }
    
        <span class="dt">double</span> findMedianSortedArrays(vector&lt;<span class="dt">int</span>&gt;&amp; nums1, vector&lt;<span class="dt">int</span>&gt;&amp; nums2) {
            <span class="dt">int</span> totalLength = nums1.size() + nums2.size();
            <span class="cf">if</span> (totalLength % <span class="dv">2</span> == <span class="dv">1</span>) {
                <span class="cf">return</span> getKthElement(nums1, nums2, (totalLength + <span class="dv">1</span>) / <span class="dv">2</span>);
            }
            <span class="cf">else</span> {
                <span class="cf">return</span> (getKthElement(nums1, nums2, totalLength / <span class="dv">2</span>) + getKthElement(nums1, nums2, totalLength / <span class="dv">2</span> + <span class="dv">1</span>)) / <span class="fl">2.0</span>;
            }
        }
}</code></pre></div>
<h2 id="两数相加">2 两数相加</h2>
<ul>
<li><strong>方法</strong>：链表</li>
<li><strong>需要注意的点</strong>:
<ol style="list-style-type: decimal">
<li>要用一个数字carry来记录进位；</li>
<li>注意判断循环终止条件；</li>
</ol></li>
</ul>
<div class="sourceCode"><pre class="sourceCode cpp"><code class="sourceCode cpp"><span class="kw">class</span> Solution {
    <span class="kw">public</span>:
        ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
            ListNode* dummy = <span class="kw">new</span> ListNode(<span class="dv">0</span>);
            ListeNode* cur = dummy;
            <span class="dt">int</span> carry = <span class="dv">0</span>;
            <span class="cf">while</span>(l1 || l2 || carry){
                <span class="dt">int</span> sum = carry;
                sum += l1 ? l1-&gt;val:<span class="dv">0</span>;
                sum += l2 ? l2-&gt;val:<span class="dv">0</span>;
                <span class="cf">if</span>(l1) l1=l1-&gt;next;
                <span class="cf">if</span>(l2) l2=l2-&gt;next;
                carry = sum /<span class="dv">10</span>;
                cur-&gt;next = <span class="kw">new</span> ListNode(sum % <span class="dv">10</span>);
                cur = cur-&gt;next;
            }
        }
}</code></pre></div>
<h2 id="快速排序">快速排序</h2>
<div class="sourceCode"><pre class="sourceCode c"><code class="sourceCode c"><span class="dt">void</span> quickSort(std::vector&lt;<span class="dt">int</span>&gt;&amp; arr, <span class="dt">int</span> left, <span class="dt">int</span> right) {
    <span class="cf">if</span> (left &gt;= right) <span class="cf">return</span>;

    <span class="dt">int</span> pivot = arr[left];
    <span class="dt">int</span> i = left + <span class="dv">1</span>;
    <span class="dt">int</span> j = right;

    <span class="cf">while</span> (i &lt;= j) {
        <span class="cf">while</span> (i &lt;= j &amp;&amp; arr[i] &lt;= pivot) i++;
        <span class="cf">while</span> (i &lt;= j &amp;&amp; arr[j] &gt;= pivot) j--;
        <span class="cf">if</span> (i &lt; j) std::swap(arr[i], arr[j]);
    }
    std::swap(arr[left], arr[j]);

    quickSort(arr, left, j - <span class="dv">1</span>);
    quickSort(arr, j + <span class="dv">1</span>, right);
}</code></pre></div>
<h2 id="归并排序">归并排序</h2>
<div class="sourceCode"><pre class="sourceCode c"><code class="sourceCode c"><span class="dt">void</span> merge(std::vector&lt;<span class="dt">int</span>&gt;&amp; arr, <span class="dt">int</span> left, <span class="dt">int</span> mid, <span class="dt">int</span> right) {
    std::vector&lt;<span class="dt">int</span>&gt; temp(right - left + <span class="dv">1</span>);
    <span class="dt">int</span> i = left, j = mid + <span class="dv">1</span>, k = <span class="dv">0</span>;

    <span class="cf">while</span> (i &lt;= mid &amp;&amp; j &lt;= right) {
        <span class="cf">if</span> (arr[i] &lt;= arr[j]) {
            temp[k++] = arr[i++];
        } <span class="cf">else</span> {
            temp[k++] = arr[j++];
        }
    }

    <span class="cf">while</span> (i &lt;= mid) {
        temp[k++] = arr[i++];
    }

    <span class="cf">while</span> (j &lt;= right) {
        temp[k++] = arr[j++];
    }

    <span class="cf">for</span> (i = left, k = <span class="dv">0</span>; i &lt;= right; ++i, ++k) {
        arr[i] = temp[k];
    }
}

<span class="dt">void</span> mergeSort(std::vector&lt;<span class="dt">int</span>&gt;&amp; arr, <span class="dt">int</span> left, <span class="dt">int</span> right) {
    <span class="cf">if</span> (left &lt; right) {
        <span class="dt">int</span> mid = left + (right - left) / <span class="dv">2</span>;
        mergeSort(arr, left, mid);
        mergeSort(arr, mid + <span class="dv">1</span>, right);
        merge(arr, left, mid, right);
    }
}</code></pre></div>
<h2 id="堆排序">堆排序</h2>
<div class="sourceCode"><pre class="sourceCode c"><code class="sourceCode c"><span class="dt">void</span> heapify(std::vector&lt;<span class="dt">int</span>&gt;&amp; arr, <span class="dt">int</span> n, <span class="dt">int</span> i) {
    <span class="dt">int</span> largest = i;
    <span class="dt">int</span> left = <span class="dv">2</span> * i + <span class="dv">1</span>;
    <span class="dt">int</span> right = <span class="dv">2</span> * i + <span class="dv">2</span>;

    <span class="cf">if</span> (left &lt; n &amp;&amp; arr[left] &gt; arr[largest]) {
        largest = left;
    }

    <span class="cf">if</span> (right &lt; n &amp;&amp; arr[right] &gt; arr[largest]) {
        largest = right;
    }

    <span class="cf">if</span> (largest != i) {
        std::swap(arr[i], arr[largest]);
        heapify(arr, n, largest);
    }
}

<span class="dt">void</span> heapSort(std::vector&lt;<span class="dt">int</span>&gt;&amp; arr) {
    <span class="dt">int</span> n = arr.size();

    <span class="cf">for</span> (<span class="dt">int</span> i = n / <span class="dv">2</span> - <span class="dv">1</span>; i &gt;= <span class="dv">0</span>; i--) {
        heapify(arr, n, i);
    }

    <span class="cf">for</span> (<span class="dt">int</span> i = n - <span class="dv">1</span>; i &gt; <span class="dv">0</span>; i--) {
        std::swap(arr[<span class="dv">0</span>], arr[i]);
        heapify(arr, i, <span class="dv">0</span>);
    }
}</code></pre></div>
</body>
</html>
